package Algoritmos;

import grafoS.Graph;

/**
 * Gcol is a program to help users to learn a little about graph coloring, in
 * this software, you can learn some coloring algorithms, and add your own
 * algorithm for coloring.You can also learn BFS and DFS search. This tool, also
 * support the .col format from DIMACS (Center for Discrete Mathematics and
 * Theoretical Computer Science), so you can import a big graph and use all the
 * algorithms. Copyright (C) <2015> Clóvis Daniel Souza Silva, Samuel Silva de
 * Souza, Professor Leonardo Sampaio Rocha.
 * 
* This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
* This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 * 
* You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 * 
 * contact: projetoGrafos@gmail.com
 */

/**
 * 
 * @author Daniel
 */

/**
 * In this class, we'll do the coloring in the graph, but following a BFS visit
 * order, it's important to say that we'll coloring just the connected vertices.
 * The colors will be integers 1 or above.
 * Any vertex not owned to the subgraph of the selected vertex will be filled
 * with -1 as it color.
 * 
 */
public class ColorirBfs extends Algorithm{

    int cor[];
    Graph graph;
    int matriz[][];

    /**
    * The ReturnColor is a virtual method from the class Algorithm.
    * @param g A graph, where we'll use the adjacency matrix.
    * @param vertice A integer, to represent the index of the vertex.
    * @return a vector with the size of the total of vertex, indicating
    * the color of each vertex.
    */
    public int[] ReturnColor(Graph g, int vertice) {
        matriz = g.getGrafo();
        cor = new int[g.getN()];
        graph = g;
        int[] aux = g.BFS(vertice+1);
        
        for (int i = 0; i < aux.length; i++) {
            colorirBySteps(aux[i]);
        }
        for(int i = 0; i< cor.length; i++)
        {
            if(cor[i] == 0)
            {
                cor[i] = -1;
            }
               
        }
        return cor;
    }

    /**
    * coloringBySteps work coloring the vector cor by index.
    * 
    * @param v The index of the vertex to coloring.
    */
    public void colorirBySteps(int v) {
        int[][] Grafo = matriz;
        int[] adjacentes = new int[graph.getN()];
        for (int i = 0; i < adjacentes.length; i++) {
            if (Grafo[v][i] == 1) {
                if (cor[v] == cor[i] && cor[v] != 0) {
                    cor[v]++;
                    i = -1;
                }
                if (cor[v] == 0) {
                    cor[v]++;
                    i = -1;
                }
            }

        }
        if (cor[v] == 0)
            cor[v]++;

    }
}

